// ----------------------------------------------------------------------------
// hash_fnv1a.cpp
// ----------------------------------------------------------------------------
// from http://isthe.com/chongo/tech/comp/fnv/#FNV-reference-source
#include <fw/base/runtime/_IMPL/hash_fnv1a.h>
#include <fw/base/core/stdinteger.h>
#include <fw/base/core/assertion.h>
#include <stddef.h>

/*
 * 32 bit magic FNV-1a prime
 */
#define FNV_32_PRIME		((uint32_t)FW_FNV1A_PRIME_32)

/*
 * 64 bit magic FNV-1a prime
 */
#define FNV_64_PRIME        ((uint64_t)FW_FNV1A_PRIME_64)
#define FNV_64_PRIME_LOW	((unsigned long)0x1b3)	/* lower bits of FNV prime */
#define FNV_64_PRIME_SHIFT	(8)						/* top FNV prime shift above 2^32 */

namespace fw
{
	namespace fnv1a
	{
		uint32_t		HashValueInternal32(const void* buf, size_t len, uint32_t hval)
		{
			FW_ASSERT(buf && len>0);
			unsigned char *bp = (unsigned char *)buf;	/* start of buffer */
			unsigned char *be = bp + len;				/* beyond end of buffer */
			
			/*
			 * FNV-1a hash each octet in the buffer
			 */
			while (bp < be) {
				
				/* xor the bottom with the current octet */
				hval ^= (uint32_t)*bp++;
				
				/* multiply by the 32 bit FNV magic prime mod 2^32 */
#if defined(NO_FNV_GCC_OPTIMIZATION)
				hval *= FNV_32_PRIME;
#else
				hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
#endif
			}
			
			/* return our new hash value */
			return hval;
		}
		
		uint64_t		HashValueInternal64(const void* buf, size_t len, uint64_t _hval)
		{
			FW_ASSERT(buf && len>0);
			typedef union
			{
				uint64_t w64;
				uint32_t w32[2]; /* w32[0] is low order, w32[1] is high order word */
			} Fnv64_t;
			Fnv64_t hval;
			hval.w64 = _hval;
			unsigned char *bp = (unsigned char *)buf;	/* start of buffer */
			unsigned char *be = bp + len;		/* beyond end of buffer */
			
#if defined(HAVE_64BIT_LONG_LONG)
			/*
			 * FNV-1a hash each octet of the buffer
			 */
			while (bp < be) {
				
				/* xor the bottom with the current octet */
				hval ^= (Fnv64_t)*bp++;
				
				/* multiply by the 64 bit FNV magic prime mod 2^64 */
#if defined(NO_FNV_GCC_OPTIMIZATION)
				hval *= FNV_64_PRIME;
#else /* NO_FNV_GCC_OPTIMIZATION */
				hval += (hval << 1) + (hval << 4) + (hval << 5) +
				(hval << 7) + (hval << 8) + (hval << 40);
#endif /* NO_FNV_GCC_OPTIMIZATION */
			}
			
#else /* HAVE_64BIT_LONG_LONG */
			
			unsigned long val[4];			/* hash value in base 2^16 */
			unsigned long tmp[4];			/* tmp 64 bit value */
			
			/*
			 * Convert Fnv64_t hval into a base 2^16 array
			 */
			val[0] = hval.w32[0];
			val[1] = (val[0] >> 16);
			val[0] &= 0xffff;
			val[2] = hval.w32[1];
			val[3] = (val[2] >> 16);
			val[2] &= 0xffff;
			
			/*
			 * FNV-1a hash each octet of the buffer
			 */
			while (bp < be) {
				
				/* xor the bottom with the current octet */
				val[0] ^= (unsigned long)*bp++;
				
				/*
				 * multiply by the 64 bit FNV magic prime mod 2^64
				 *
				 * Using 0x100000001b3 we have the following digits base 2^16:
				 *
				 *	0x0	0x100	0x0	0x1b3
				 *
				 * which is the same as:
				 *
				 *	0x0	1<<FNV_64_PRIME_SHIFT	0x0	FNV_64_PRIME_LOW
				 */
				/* multiply by the lowest order digit base 2^16 */
				tmp[0] = val[0] * FNV_64_PRIME_LOW;
				tmp[1] = val[1] * FNV_64_PRIME_LOW;
				tmp[2] = val[2] * FNV_64_PRIME_LOW;
				tmp[3] = val[3] * FNV_64_PRIME_LOW;
				/* multiply by the other non-zero digit */
				tmp[2] += val[0] << FNV_64_PRIME_SHIFT;	/* tmp[2] += val[0] * 0x100 */
				tmp[3] += val[1] << FNV_64_PRIME_SHIFT;	/* tmp[3] += val[1] * 0x100 */
				/* propagate carries */
				tmp[1] += (tmp[0] >> 16);
				val[0] = tmp[0] & 0xffff;
				tmp[2] += (tmp[1] >> 16);
				val[1] = tmp[1] & 0xffff;
				val[3] = tmp[3] + (tmp[2] >> 16);
				val[2] = tmp[2] & 0xffff;
				/*
				 * Doing a val[3] &= 0xffff; is not really needed since it simply
				 * removes multiples of 2^64.  We can discard these excess bits
				 * outside of the loop when we convert to Fnv64_t.
				 */
			}
			
			/*
			 * Convert base 2^16 array back into an Fnv64_t
			 */
			hval.w32[1] = (uint32_t)((val[3]<<16) | val[2]);
			hval.w32[0] = (uint32_t)((val[1]<<16) | val[0]);
			
#endif /* HAVE_64BIT_LONG_LONG */
			
			/* return our new hash value */
			return hval.w64;
		}
		
	} // namespace murmur
} // namespace fw

